1. Field of the Invention
The present invention relates to the design of memory hierarchies within computer systems. More specifically, the present invention relates to a method and an apparatus for using references within an object to prefetch other objects into an object cache.
2. Related Art
As the gap between memory speed and processor speed grows ever larger, programs that access data structures that are too large to fit into cache memory incur progressively larger performance penalties. To alleviate this problem, some computer systems employ a hardware prefetcher that looks for patterns of memory accesses. When such a pattern is discovered, the prefetcher prefetches ahead of the program to ensure that the needed data will be present in cache.
Prefetchers work relatively well for programs with regular memory access patterns, such as scientific applications that manipulate large arrays of data. However, they work poorly for object-oriented or pointer-based applications, such as programs written in the JAVA programming language. In pointer-based applications, the next data element to be retrieved by the application is not located at a regular offset from the current data element, because a pointer can generally refer to an arbitrary location in memory.
Moreover, because pointers cannot presently be identified within cache lines, existing prefetching systems must rely on heuristics to guess which words in a cache line contain pointers that are worth prefetching.
Furthermore, even when such a pointer can be identified, the pointer is in the form of virtual addresses, which must first be translated into a physical address before a prefetching operation can take place. This translation process takes additional time.
What is needed is a method and an apparatus for prefetching cache lines for object-oriented and/or pointer-based applications that overcomes the above-described problems.
One embodiment of the present invention provides a system that uses references within a first object to prefetch a second object into a cache memory. During operation, the system receives a first cache line containing at least a portion of the first object. Next, the system locates a reference to the second object within the first cache line, and uses the reference to perform a prefetching operation for the second object.
In a variation on this embodiment, while performing the prefetching operation for the second object, the system examines the cache memory to determine if the second object is already present within the cache memory. If not, the system performs the prefetching operation for the second object.
In a variation on this embodiment, locating the reference to the second object involves examining type information associated with data items in the first cache line to determine whether the data items contain references.
In a variation on this embodiment, locating the reference to the second object involves using the offsets of data items within the first object to determine whether the data items contain references.
In a variation on this embodiment, locating the reference to the second object involves locating a class pointer within the first object that points to a class object associated with the first object.
In a variation on this embodiment, performing the prefetching operation for the second object involves prefetching a second cache line containing at least a portion of the second object.
In a variation on this embodiment, performing the prefetching operation for the second object involves prefetching an object table entry for the second object. This object table entry maps an object ID to an address where the second object is located.
In a variation on this embodiment, if the first cache line contains only a portion of the first object, the system prefetches another portion of the first object. Note that this may involve prefetching a header for the first object.
In a variation on this embodiment, the first object and the second object are defined within an object-oriented programming system.